package com.cqs.leetcode.backtrack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author lixqw
 * @date 2020/9/7
 */
public class PalindromePartitioning131 {


    public List<List<String>> partition(String s) {
        List<List<String>> list = new ArrayList<>();
        partition(s, 0, new Stack<>(), list);
        return list;
    }


    private void partition(String s, int level, Stack<String> tmp, List<List<String>> list) {
        if (s.length() == level) {
            list.add(new ArrayList<>(tmp));
            return;
        }
        for (int i = level; i < s.length(); i++) {
            //作为前缀
            if (!isPalindrome(s, level, i)) {
                continue;
            }
            tmp.push(s.substring(level, i + 1));
            partition(s, i+1, tmp, list);
            tmp.remove(tmp.size() - 1);
        }

    }

    private boolean isPalindrome(String s, int left, int right) {
        int i = left, j = right;
        while (i < j) {
            if (s.charAt(i++) != s.charAt(j--)) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        List<String> tests = new ArrayList<>();
        tests.add("abcb");
        tests.add("aba");
        tests.add("aaaa");
        PalindromePartitioning131 pp = new PalindromePartitioning131();
        tests.forEach(it -> {
            List<List<String>> partition = pp.partition(it);
            System.out.println(it + "\t" + partition);
        });
    }
}
